const MOD = 10**9 + 7;

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void async function () {
    let t = Number(await readline());
    while (t--) {
        let n = Number(await readline());
        let s = await readline();
        // console.log(n, s)
        let dp = Array(n + 1).fill(0);
        dp[0] = 1;  // 空字符串有一种合法分割方式
        if(n === 1) {
            if( s !== '0' ) {
                console.log(1);
            } else {
                console.log(0);
            }
            continue
        }
        for (let i = 1; i <= n; i++) {
            // 遍历所有可能的分割点
            for (let j = i - 1; j >= i - 2; j--) {
                let substring = s.slice(j, i);
                if (substring[0] !== '0' && (substring.length === 1 || parseInt(substring) <= 26)) {
                    dp[i] = (dp[i] + dp[j]) % MOD;
                }
            }
        }
        console.log(dp[n]);
    }
}();
